//给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 
//
// 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。 
//
// 
//
// 示例 1: 
//
// 
//输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 
//
// 示例 2: 
//
// 
//输入: strs = [""]
//输出: [[""]]
// 
//
// 示例 3: 
//
// 
//输入: strs = ["a"]
//输出: [["a"]] 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 10⁴ 
// 0 <= strs[i].length <= 100 
// strs[i] 仅包含小写字母 
// 
// Related Topics 哈希表 字符串 排序 👍 973 👎 0

package leetcode.editor.cn;

import com.sun.org.apache.xalan.internal.xsltc.compiler.SourceLoader;
import com.sun.org.apache.xalan.internal.xsltc.compiler.util.StringStack;

import java.awt.print.Pageable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//Java：字母异位词分组
class GroupAnagrams{
    public static void main(String[] args) {
        Solution solution = new GroupAnagrams().new Solution();
        // TO TEST
        String[] strs = {"abc", "bac", "aaa"};
        solution.groupAnagrams(strs);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)

/**
 * 两种解法：
 * 1.利用排序，异位词字母的个数和顺序一样,时间复杂度：O(nklogk)
 * 2.用数组统计字符串字符个数，异位词字母+出现个数,时间复杂度：O(nk)
 *
 * 笔记：
 * 1.map.getDefault
 * */
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null) {
            return null;
        }
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            //用来存储字符串的字母个数
            int[] countArray = new int[26];
            for (int i = 0; i < str.length(); i++) {
                //字母下标0-25
                Integer index = str.charAt(i) - 'a';
                countArray[index]++;
            }
            //将出现的字母及其出现次数按字母顺序拼字符串,eg:a3b4c5
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                if (countArray[i] != 0) {
                    sb.append((char)('a' + i));
                    sb.append(countArray[i]);
                }
            }
            //找不到时新建一个value
            List<String> list = map.getOrDefault(sb.toString(), new ArrayList<String>());
            list.add(str);
            map.put(sb.toString(), list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
